/*
 * main.c
 * Author: lakshmanas
 */

#include <stdio.h>
#include <stdlib.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2

#define TREE 0
#define BACK 1
#define CROSS 2
#define FORWARD 3

int n; // number of nodes
int e; // number of edges

// structure to hold the edge information
struct edge {
    int tail, head, type,capacity;
};

typedef struct edge edgeType;

edgeType *edgeTab;

//pointer holding the index to the first edge of each node
int *firstEdge; // Table indicating first in range of edges with a common tail


int *discovery, *finish, *predecessor, *vertexStatus;

//file pointer to read input from file
FILE *file;


//stack holding the edge for each identified path
struct stack {
    edgeType *edge;
    struct stack *next;
};

//stack count
int stack_count=0;
//number of back edge in order to identify cycle
int back_edge_count=0;
int path_length=0;
int path_count=0;
int flow_count=0;

typedef struct stack stackEdgeType;
//pointer to the head of the stack
stackEdgeType *head=NULL;

// pointer to  the head and last of the edge in the list which forms the cycle
stackEdgeType *cycleEdges_head=NULL;
stackEdgeType *cycleEdges_last=NULL;


//declaring pop function as it's return type is poiner
stackEdgeType* pop();



// Reading the input file and organize adjacency lists

int tailThenHead(const void* xin, const void* yin)
// Used in calls to qsort() and bsearch() for read_input_file()
{
    int result;
    edgeType *x, *y;

    x = (edgeType*) xin;
    y = (edgeType*) yin;
    result = x->tail - y->tail;
    if (result != 0)
        return result;
    else
        return x->head - y->head;
}

/**
 * function to read the input from the file , input is
 * 1. no of nodes, edges.
 * 2. edge tail and head and capacity
 */

void read_input_file() {
    int a, b,c, i, j;
    edgeType work;
    edgeType *ptr;

    file = fopen("input1.dat","r");
    //scanf("%d %d", &n, &e);
    fscanf(file,"%d %d", &n, &e);
    edgeTab = (edgeType*) malloc(e * sizeof(edgeType));
    if (!edgeTab) {
        printf("edgeTab malloc failed %d\n", __LINE__);
        exit(0);
    }

    for (i = 0; i < e; i++) {
        //scanf("%d %d %d", &a, &b,&c);
        fscanf(file,"%d %d %d", &a, &b,&c);
        if (a < 0 || a >= n || b < 0 || b >= n) {
            printf("Invalid input %d %d at %d\n", a, b, __LINE__);
            exit(0);
        }
        edgeTab[i].tail = a;
        edgeTab[i].head = b;
        edgeTab[i].capacity = c;
        if(a==0)
        	flow_count+=c;
    }

// sort edges
    qsort(edgeTab, e, sizeof(edgeType), tailThenHead);

// Coalesce duplicates into a single edge
    j = 0;
    for (i = 1; i < e; i++)
        if (edgeTab[j].tail == edgeTab[i].tail
                && edgeTab[j].head == edgeTab[i].head)
            ;
        else {
            j++;
            edgeTab[j].tail = edgeTab[i].tail;
            edgeTab[j].head = edgeTab[i].head;
        }
    e = j + 1;

// For each vertex as a tail, determine first in range of edgeTab entries
    firstEdge = (int*) malloc((n + 1) * sizeof(int));
    if (!firstEdge) {
        printf("malloc failed %d\n", __LINE__);
        exit(0);
    }
    j = 0;
    for (i = 0; i < n; i++) {
        firstEdge[i] = j;
        //printf("firstEdge[%d]=%d",i,j);
        for (; j < e && edgeTab[j].tail == i; j++)
            ;
    }
    firstEdge[n] = e;
    fclose(file);
}


/**
 * this mehtod finds the  path from starting node(s) to end node (t), using the DFS
 *	s-start node
 *	n-end ndode
 */
int find_S_T_path(int s, int t) {
    int path_length=0;
    int i,u=s,v=0,c;
    vertexStatus[s]=GRAY;

    while(1) {
        i=firstEdge[u];
        for(; i<firstEdge[u+1] && u!=t;) {
            v=edgeTab[i].head;
            c=edgeTab[i].capacity;
            if( vertexStatus[v]==WHITE && edgeTab[i].capacity>0) {
                vertexStatus[v]=GRAY;
                stackEdgeType  *elem= (stackEdgeType*)malloc(sizeof(stackEdgeType));
                elem->edge=&edgeTab[i];
                elem->next=NULL;
                push(elem);
                path_length++;
                //v=u;
                i=firstEdge[v];
                u=v;
            }
            else {
                i++;
            }
        }
        if(v==t && c>0) {
            // printf("\nfoudn S-T path %d %d \n",s,t);
            //show_stack();
            return 1;
        }
        else {
            path_length--;

            stackEdgeType *ele =pop();
            if(ele!=NULL) {
                u=ele->edge->tail;
                //printf("poping one level up to node: %d \n",u);
            }
            else {
                //printf("\npath not found from %d %d",s,t);
                return 0;
            }
        }
    }
    return 0;
}



/**
 * this mehtod iteratively finds all paths from starting node to end node
 * 	s-start node
 * 	n-end node
 */
void find_all_S_T_pahts(int s, int t) {
    int res=0;
    printf("\nflow decomposition: saturated edges <=, unsaturated edges <- , edges are seperated by -\n");
    do {
        clear_vertex_status();
        res=find_S_T_path(s,t);
        if(res)
            find_smallest_path_reduce();
    } while(res);
    //printf("\n exiting find path\n");
}


/**
 * this method clears the vertex or node status from being visited to not visited
 * after each path is found  or DFS
 */
void clear_vertex_status() {
    int u;
    head=NULL;
    stack_count=0;
    //cycleEdges=NULL;
    for (u = 0; u < n; u++) {
        vertexStatus[u] = WHITE;
    }
}


/**
 * this method traverse the graph using DFS method and while traversing
 * if a back edge is found, it addes it to the list of back edges (cycleEdges)
 */
int time; /*Keeps node numbering*/
void DFS_graph_traverse(int u)
{
    int i, v,c;

    if(vertexStatus[u]==WHITE) {
        discovery[u] = time;
    }
    time++;
    vertexStatus[u] = GRAY;
    for (i = firstEdge[u]; i < firstEdge[u + 1]; i++) {
        stackEdgeType  *elem= (stackEdgeType*)malloc(sizeof(stackEdgeType));
        elem->edge=&edgeTab[i];
        elem->next=NULL;
        v = edgeTab[i].head;
        c=edgeTab[i].capacity;
        //printf("\nvisiting edge %d %d %d %d",edgeTab[i].tail, edgeTab[i].head,edgeTab[i].capacity,vertexStatus[v]);
        if (vertexStatus[v] == WHITE ) {
            //printf("\nedge is white");
            edgeTab[i].type = TREE;
            predecessor[v] = u;
            //add_to_cycle_edge(elem);
            DFS_graph_traverse(v);
        } else if (vertexStatus[v] == GRAY) {
            //printf("\nedge is black");
            if(edgeTab[i].type !=BACK) {
                edgeTab[i].type =BACK;
                add_to_cycle_edge(elem);
            }
        }
        else if (discovery[u] < discovery[v]) {
            edgeTab[i].type = FORWARD;
            //printf("\nedge is black");
            predecessor[v] = u;
            DFS_graph_traverse(v);

        }
        else {
            //printf("\ncheckign edge for black");
            if(edgeTab[i].type !=BACK) {
                edgeTab[i].type =BACK;
                add_to_cycle_edge(elem);
            }
        }
    }
    vertexStatus[u] = BLACK;
    time++;
    finish[u] = time;
}

/**
 * this method first  iterates the list of back edges, then for
 * each back edge it finds the path from starting node to end node which forms the back edge
 * then it removes the lowest path capacity in the cycle
 */
void removeCycle() {
    stackEdgeType *temp= cycleEdges_head;
    int res;
    while(temp!=NULL) {
        int s=temp->edge->head;
        int t=temp->edge->tail;
        do {
            res=0;
            clear_vertex_status();
            //printf("\n canceling smallest flow allong all edges in cycle (%d,%d, %d)\n",s,t,temp->edge->capacity);
            if(temp->edge->capacity>0) {
                //finds the back edge path
                res =find_S_T_path(s,t);
            }
            if(res==1) {
                stackEdgeType *back_edge = (stackEdgeType*) malloc(sizeof(stackEdgeType));
                back_edge->edge=temp->edge;
                back_edge->next=NULL;
                push(back_edge);
                //reduces the lowest path capacity in the edge
                find_smallest_cycle_reduce();
            }
        }
        while(res);
        temp=temp->next;
    }
}


/**
 * this method finds the smallest edge in the cycle and reduces it's capacity for all edges in the cycle
 */
void find_smallest_cycle_reduce() {
    stackEdgeType *temp=head;
    stackEdgeType *min=temp;

    while(temp!=NULL) {
        if(temp->edge->capacity<min->edge->capacity) {
            min=temp;
        }
        temp=temp->next;
    }
    printf("\nCancel cycle of %d edges, limiting edge %d->%d has flow %d\n",stack_count, min->edge->tail,min->edge->head,min->edge->capacity);
    temp=head;
    int min_cap=min->edge->capacity;
    while(temp!=NULL) {
        printf("\n%d->%d before flow %d ",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        temp->edge->capacity-=min_cap;
        printf("after flow is %d \n",temp->edge->capacity);
        temp=temp->next;
    }
}


/**
 * this method finds the smallest edge in the path(s-t) and reduces it's capacity for all edges in the path from s-t
 */
void find_smallest_path_reduce() {

    stackEdgeType *temp=head;
    stackEdgeType *min=temp;

    while(temp!=NULL) {
        if(temp->edge->capacity<min->edge->capacity) {
            min=temp;
        }
        temp=temp->next;
    }
    //printf("\n reducing smallest flow in the path  %d between (%d,%d) \n",min->edge->capacity,min->edge->tail,min->edge->head);
    temp=head;
    int min_cap=min->edge->capacity;
    flow_count+=min_cap;
    printf("\n %d :",++path_count);
    while(temp!=NULL) {
    	temp->edge->capacity-=min_cap;
    	if(temp->edge->capacity <= 0)
    		printf("%d<=", temp->edge->head);
        else
    	   printf("%d<-", temp->edge->head);
        if(temp->next != NULL)
        {
        }
        else
        {
        	printf("%d", temp->edge->tail);
    	    printf(" flow: %d\n", min_cap);
    	}

        // printf("\n%d %d %d\n",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        temp=temp->next;
    }
}

/**
 * this mehtod puses the edge into the stack which forms the path from s to t
 */
void push(stackEdgeType *elem) {
    stack_count++;
    if(head==NULL) {
        head=elem;
        head->next=NULL;
    }
    else {
        elem->next=head;
        head=elem;
    }
    //printf("\npushing edge :");
    //printf("%d %d %d \n" ,elem->edge->tail,elem->edge->head,elem->edge->capacity);

}

/**
 * this method pops the edge from the stack
 */
stackEdgeType* pop()
{
    stack_count--;
    if(head==NULL) {
        return NULL;
    }
    stackEdgeType *temp =head;
    //printf(" poping edge %d %d %d\n" ,temp->edge->tail,temp->edge->head,temp->edge->capacity);
    head=head->next;
    temp->next=NULL;
    return temp;
}

/**
 * this method displays the edges in the stack
 */
void show_stack() {
    stackEdgeType *temp = head;
    printf("\n stack elements are \n");
    printf("\nt h c\n");
    while(temp!=NULL) {
        printf("%d %d %d  \n" ,temp->edge->tail,temp->edge->head,temp->edge->capacity);
        //printf("(%d<-%d)",temp->edge->head,temp->edge->tail);
        //if(temp->next!=NULL)
        //  printf(",");
        temp=temp->next;
    }
}

/**
 * this method adds the back edge found while traversing the grpah to the list of back edges
 */
void add_to_cycle_edge(stackEdgeType *elem) {
    back_edge_count++;
    if(cycleEdges_head==NULL) {
        cycleEdges_head=elem;
        cycleEdges_last=elem;
    }
    else {
        cycleEdges_last->next=elem;
        cycleEdges_last=elem;
    }
    //printf("\nadding back edge (%d->%d, %d)\n" ,elem->edge->tail,elem->edge->head,elem->edge->capacity);
}


/**
 * this method removes the back edge found while traversing the grpah to the list of back edges
 */
void removed_cycle_edges() {
    while(cycleEdges_head!=NULL) {
        stackEdgeType *temp = cycleEdges_head;
        //printf("\nremoving cycle edge %d %d %d\n",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        cycleEdges_head=cycleEdges_head->next;
        temp->next=NULL;
        push(temp);
    }
}



int main() {
    int u, i, j, k, nextDFS;

    read_input_file();
    discovery = (int*) malloc(n * sizeof(int));
    finish = (int*) malloc(n * sizeof(int));
    predecessor = (int*) malloc(n * sizeof(int));
    vertexStatus = (int*) malloc(n * sizeof(int));
    if (!discovery || !finish || !predecessor || !vertexStatus) {
        printf("malloc failed\n");
        exit(0);
    }

    // DFS code, initially seeting all vertex to WHITE
    for (u = 0; u < n; u++) {
        vertexStatus[u] = WHITE;
        predecessor[u] = (-1);
    }
    time = 0;
    for (u = 0; u < n; u++) {
        if (vertexStatus[u] == WHITE) {
            DFS_graph_traverse(u);
        }
    }
    printf("\nVerified flow is : %d ",flow_count);
    flow_count=0;
    //remove cycle and lowest capacity
    removeCycle();

    // find all s-t path and reduce lowest capacity in the path
    find_all_S_T_pahts(0,n-1);
    printf("\n Total flow in decomposition : %d ",flow_count);

    //Output code
    /*
    printf("Vertex  discovery    finish     predecessor\n");
    for (i = 0; i < n; i++)
    	printf(" %3d      %3d         %3d          %3d\n", i, discovery[i],finish[i], predecessor[i]);

    printf("edges after removing cycle and flow decomposition");
    printf("\nEdge 	Tail 	Head 	capacity\n");
    for (i = 0; i < e; i++) {
        printf(" %3d  %3d  %3d  %3d  ", i, edgeTab[i].tail, edgeTab[i].head,edgeTab[i].capacity);
        switch (edgeTab[i].type) {
        case TREE:
            printf("tree\n");
            break;
        case BACK:
            printf("back\n");
            break;
        case CROSS:
            printf("cross\n");
            break;
        case FORWARD:
            printf("forward\n");
            break;
        }
    }
	*/
    free(edgeTab);
    free(firstEdge);
    free(discovery);
    free(finish);
    free(predecessor);
    free(vertexStatus);
    free(head);
    free(cycleEdges_head);
    free(cycleEdges_last);
    return 0;
}
